|
In combinatorial mathematics and statistics, the Fuss–Catalan numbers are numbers of the form : They are named after N. I. Fuss and Eugène Charles Catalan. In some publications this equation is sometimes referred to as Two-parameter Fuss–Catalan numbers or Raney numbers. The implication is the ''single-parameter Fuss-Catalan numbers'' are when =1. ==Uses== The Fuss-Catalan represents the number of legal permutations or allowed ways of arranging a number of articles, that is restricted in some way. This means that they are related to the Binomial Coefficient. The key difference between Fuss-Catalan and the Binomial Coefficient is that there are no "illegal" arrangement permutations within Binomial Coefficient, but there are within Fuss-Catalan. An examples of legal and illegal permutations can be better demonstrated by a specific problem such as balanced brackets (see Dyck language). A general problem is to count the number of balanced brackets (or legal permutations) that a string of ''2m'' brackets forms. By legally arranged, the following rules apply: * For the sequence as a whole, the number of open brackets must equal the number of closed brackets * Working along the sequence, the difference between the number of open and closed brackets cannot be negative As an numeric example how many combinations can 6 brackets be legally arranged? From the Binomial interpretation there are or numerically = 20 ways of arranging 3 open and 3 closed brackets. However, there are fewer ''legal'' combinations than these when all of the above restrictions apply. Evaluating these by hand, there are 5 legal combinations, namely: ()()(); (())(); ()(()); (()()); ((())). This corresponds to the Fuss-Catalan formula when ''p=2, r=1'' which is the Catalan number formula or =5. By simple subtraction, there are or =15 illegal combinations. To further illustrate the subtlety of the problem, if one were to persist with solving the problem just using the Binomial formula, it would be realised that the 2 rules imply that the sequence must start with an open bracket and finish with a closed bracket. This implies that there are or =6 combinations. This is inconsistent with the above answer of 5, and the missing combination is: ())((), which is illegal and would complete the binomial interpretation. Whilst the above is a concrete example Catalan numbers, similar problems can be evaluated using Fuss-Catalan formula: * Computer Stack: ways of arranging and completing a computer stack of instructions, each time step 1 instruction is processed and p new instructions arrive randomly. If at the beginning of the sequence there are r instructions outstanding. * Betting: ways of losing all money when betting. A player has a total stake pot that allows them to make r bets, and plays a game of chance that pays p times the bet stake. * Tries: Calculating the number of order ''m'' tries on ''n'' nodes. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Fuss–Catalan number」の詳細全文を読む スポンサード リンク
|